
//475.供暖器
class Solution {

     //检查当前x时候满足条件
    bool check(vector<int>& houses,vector<int>& heaters,int x)
    {
        int n=houses.size(),m=heaters.size();
        int j=0;
        for(int i=0;i<n;i++)
        {
            if(houses[i]>=heaters[j]-x&&houses[i]<=heaters[j]+x) continue;
            while(j<m&&houses[i]>heaters[j]+x) j++;

            if(j==m||houses[i]<heaters[j]-x) return false;
        }
        return true;
    }

public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        //先对两个数组进行排序
        sort(houses.begin(),houses.end());
        sort(heaters.begin(),heaters.end());
        int left=-1,right=1000000000;  //设置上下边界
        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(check(houses,heaters,mid)) right=mid;
            else left=mid;
        }
        return right;
    }
};